600. Non-negative Integers without Consecutive Ones

1. Question

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

2. Examples

Example 1:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Example 2:

Input: n = 1
Output: 2

Example 3:

Input: n = 2
Output: 3

3. Constraints

• 1 <= n <= 10⁹

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

斐波那契数列

class Solution {
    public int findIntegers(int n) {
        int ans = 0;
        // 斐波那契数列
        int[] arr = new int[31];
        arr[0] = 1;
        // 只有一个数的时候有2个值符合要求
        arr[1] = 2;
        arr[2] = 3;

        for (int i = 3; i < 31; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }

        String str = Integer.toBinaryString(n);

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                continue;
            } else {
                ans += arr[str.length() - i - 1];
            }
            // 有两个重复的1
            if (i > 0 && str.charAt(i - 1) == '1') {
                return ans;
            }
        }
        return ans+1;
    }
}